bzoj1912 [Apio2010]patrol 巡逻

发表于

加一条边形成一个环，环上的边可以少走一次
k=1时直接找直径
k=2时先找一条直径，连一条边，此时如果再要经过这个环上的边，答案要加2，所以将之前找的边置为-1再找一次直径（简单证明：1)如果答案包含一条直径：注意到第一次找直径的时候可能存在多条。假如存在一条直径与第一次选的直径没有边交集，第二次就会选择那一条；假如所有直径都与它有边交集，注意到有交集的直径都是相同的（不管是点交集还是边交集），不然存在更长的链，所以随便选的那一条没有问题。2)答案不包含直径。这是不可能的。如果选的两条都不经过直径，则将一条换成直径更优；如果选的有一条经过直径，则换成直径更优；如果两条都经过直径，可以换成一条直径加一个环，答案不会更劣。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=100008;
int n,k;
int x,y;
int nume,head[N];
struct edge{
    int to,nxt,f;
}e[N<<1];
inline void add_edge(int x,int y,int z)
{
    e[++nume]=(edge){y,head[x],z};head[x]=nume;
}
int ans,tmp;
int s1[N],s2[N],mx;
inline int dfs(int x,int fa)
{
    int mx1=0,mx2=0; 
    for(int i=head[x];i;i=e[i].nxt){
        if(e[i].to!=fa){
            int t=dfs(e[i].to,x)+e[i].f;
            if(t>mx1){
                mx2=mx1;
                mx1=t;
                s2[x]=s1[x];
                s1[x]=i;
            }
            else if(t>mx2){
                mx2=t;
                s2[x]=i;
            }
        }
    }
    if(mx1+mx2>tmp){
        tmp=mx1+mx2;
        mx=x;
    }
    return mx1;
}
int main()
{
    nume=1;
    n=read();k=read();
    ans=2*(n-1);
    for(int i=1;i<n;++i){
        x=read();y=read();
        add_edge(x,y,1);
        add_edge(y,x,1); 
    }
    dfs(1,0);
    ans=ans-tmp+1;
    if(k==2){
        for(int i=s1[mx];i;i=s1[e[i].to])   e[i].f=e[i^1].f=-1;
        for(int i=s2[mx];i;i=s1[e[i].to])   e[i].f=e[i^1].f=-1;
        tmp=0;
        dfs(1,0);
        ans=ans-tmp+1;
    }
    printf("%d",ans);
    return 0;
}